package demo7;

import java.util.Arrays;
import java.util.PriorityQueue;

public class MyHeap {
    public int[] arr;
    public int usedSize;
    public MyHeap() {
        this.arr = new int[10];
    }

    public void initArr(int[] array) {
        for(int i = 0; i < array.length; i++) {
            arr[i] = array[i];
            usedSize++;//别忘了
        }
    }

    public void createMaxHeap() {
        for(int parent = (arr.length - 1 - 1) / 2 ; parent >= 0; parent--) {
            //从最后一棵子树开始，使用向下调整
            softDown(parent, this.usedSize);
        }
    }

    private void softDown(int parent, int usedSize) {
        //计算左子树
        int child = parent * 2 + 1;
        while(child < usedSize) {
            if(child + 1 < usedSize && arr[child] < arr[child + 1]) {
                child++;
            }
            if(arr[child] > arr[parent]) {
                //交换
                int tmp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }
    public void offer(int val) {
        if(isFull()) {
            arr = Arrays.copyOf(arr,usedSize * 2);
        }
        arr[usedSize] = val;
        softUp(usedSize);
        usedSize++;
    }

    private boolean isFull() {
        return  usedSize == arr.length;
    }

    private void softUp(int child) {
        int parent = (child - 1) / 2;
        while(child != parent) {
            if(arr[child] > arr[parent]) {
                int tmp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }
    private void swap(int[] arr, int j, int i) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public int poll() {
        if(isEmpty()) {
            throw new RuntimeException("堆为空！");
        }
        int ret = arr[0];
        swap(arr,0,usedSize);
        usedSize--;
        softDown(0,usedSize);
        return ret;
    }
    public int peek() {
        if(isEmpty()) {
            throw new RuntimeException("堆为空！");
        }
        return arr[0];
    }
    public void heapSort() {
        //从小到大排序
        //1.建立大根堆
        //2.交换
        while(usedSize > 0) {
            swap(arr, 0, usedSize - 1);
            softDown(0, usedSize - 1);
            usedSize--;
        }

    }

    private boolean isEmpty() {
        return usedSize == 0;
    }

}
